BOJ_9095_1,2,3 더하기

DP(Dynamic Programming)의 전형적인 문제 중 하나
dp 배열을 만들고 작은 수부터 하나씩 값을 구해 규칙을 발견하였다

dp[4]가 있다면 3이 가질 수 있는 모든 경우에 + 1을, 2는 +2를, 1은 +3을 해주고 이 모든 경우를 더해주면 dp[4]를 만들 수 있을 것이다. 따라서 n이 3보다 큰 경우 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]이 성립하게 된다

package BJO;  
  
import java.util.Scanner;  
  
public class BJO_9095_123더하기 {  
  
    public static void main(String[] args) {  
       // 5 -> dp[4] + dp[3] + dp[2]  
       Scanner scan = new Scanner(System.in);  
       int T = scan.nextInt();  
  
       for (int i = 0; i < T; i++) {  
          int n = scan.nextInt();  
  
          int[] dp = new int[n + 4];  
  
          dp[1] = 1;  
          dp[2] = 2;  
          dp[3] = 4;  
          dp[4] = 7;  
  
          for (int j = 5; j <= n; j++) {  
             dp[j] = dp[j - 1] + dp[j - 2] + dp[j - 3];  
          }  
  
          System.out.println(dp[n]);  
       }  
    }  
}

#dp